/*
 * $Id$
   Copyright 2005-2009 Chung, Hyung-Hwan.

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an  BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
 */

#ifndef _XP_BAS_BINARYSEARCHTREE_CLASS_
#define _XP_BAS_BINARYSEARCHTREE_CLASS_

#include <xp/types.h>
#include <xp/macros.h>
#include <xp/bas/assert.h>

XP_BEGIN_NAMESPACE2 (xp, bas)

template <typename T>
class BinarySearchTreeNode: protected MemoryPoolable
{
public:
	T value;
	BinarySearchTreeNode<T>* parent;
	BinarySearchTreeNode<T>* left_child;
	BinarySearchTreeNode<T>* right_child;

	BinarySearchTreeNode ():
		parent (XP_NULL), left_child (XP_NULL), right_child (XP_NULL)
	{
	}

	BinarySearchTreeNode (const T& value): value (value), 
		parent (XP_NULL), left_child (XP_NULL), right_child (XP_NULL)
	{
	}

};

template <typename T>
class BinarySearchTree
{
protected:
	MemoryPool mp;
	Node*     root;
	xp_size_t size;

public:
	typedef BinarySearchTreeNode<T> Node;

	~BinarySearchTree ()
	{
		clearout ();
	}

	BinarySearchTree (): root (XP_NULL), size (0)
	{
	}

	BinarySearchTree (const BinarySearchTree<T>& tree)
	{
	}

	BinarySearchTree<T>& operator= (const BinarySearchTree<T>& tree)
	{
	}

	void insert (const T& v)
	{
		Node* n = mp.isEnabled()? (new(&mp) Node(v)): (new Node(v));
		insert_node (n);
	}

	bool remove (const T& v)
	{
		bool is_left;

		// find the node starting from root.
		node = this->root;
		while (node != XP_NULL)
		{
			if (v < node->value) 
			{
				is_left = true;
				node = node->left;
			}
			else if (v > node->value)
			{
				is_left = false;
				node = node->right;
			}
			else
			{
				if (is_left)
				{
					node->parent->left = node->left;
				}
				else
				{
					node->parent->right = node->left;
				}

				this->size--;
				return true;
			}
		}

		return false;
	}

	Node* predecessorOf (Node* node)
	{
		// find the node with the maximum value 
		// less than the given node value.
	}

	Node* successorOf (Node* node)
	{
		// find the node with the minimum value 
		// greater than the given node value.

		Node* x = node->right;
		while (x != XP_NULL)
		{
			if (x->left == XP_NULL) return x;
			x = x->left;
		}
		return x;
	}

	void clear ()
	{
		// TODO:
	}

	void clearout ()
	{
		clear ();
		mp.dispose ();
	}


protected:
	void insert_node (Node* node)
	{
		if (this->root == XP_NULL) 
		{
			XP_ASSERT (this->size == 0);
			// the root node is NULL, this node is the
			// first node to be added. nothing much to do
			// except updating the root node itself
			this->root = cur;
		}
		else
		{
			Node* cur = this->root;

			// starting from the root node, find the right
			// place to insert the node.

			do
			{
				if (node->value < cur->value)
				{
					// traverse to the left child
					// as the node value is less.

					if (cur->left == XP_NULL)
					{
						// however, the child is NULL.
						// this is the insertion point.
						cur->left = node;
						node->parent = cur;
						break;
					}

					cur = cur->left;
				}
				else
				{
					// traverse to the left child
					// as the node value is greater 

					if (cur->right == XP_NULL)
					{
						// however, the child is NULL.
						// this is the insertion point.
						cur->right = node;
						node->parent = cur;
						break;
					}

					cur = cur->right;
				}
			}
			while (true);
		}

		this->size++;
	}
};

XP_END_NAMESPACE2 (xp, bas)

#endif
